/*
 * @lc app=leetcode.cn id=10 lang=golang
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	res := make([][]bool, m+1)
	// 注意初始化数组
	for i, _ := range res {
		res[i] = make([]bool, n+1)
		if i == 0 {
			res[0][0] = true
			for j := 1; j <= n; j++ {
				// j 对应字符
				if p[j-1] != '*' {
					res[i][j] = false
				} else {
					res[i][j] = res[i][j-2]
				}
			}
		}
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == p[j-1] || p[j-1] == '.' {
				res[i][j] = res[i-1][j-1]
			} else if p[j-1] == '*' {
				if p[j-2] == s[i-1] || p[j-2] == '.' {
					res[i][j] = res[i-1][j] || res[i][j-2]
				} else {
					res[i][j] = res[i][j-2]
				}
			} else {
				res[i][j] = false
			}
		}
	}
	return res[m][n]

}

// @lc code=end
